package 剑指offer;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Offer12_JZ65 {
    public static void main(String[] args) {
        System.out.println(hasPath("ABCESFCSADEE",3,4,"ABCB"));
    }


    public static boolean hasPath (String matrix, int rows, int cols, String str) {
        if (matrix.length() == 0) return false;
        int[][] visited = new int[rows][cols];
        int i = 0;
        char[][] chars = new char[rows][cols];
        while (i < matrix.length()) {
            int index = i/4;
            chars[index][i%4] = matrix.charAt(i);
            i++;
        }
        for (int m=0; m<rows; m++) {
            for (int n=0; n<cols; n++) {
                int pathLength = 0;
                if (solve(visited, chars, rows, cols, m, n, str, pathLength)) {
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean solve(int[][] visited, char[][] chars, int rows, int cols, int row, int col, String str, int pathLength) {
        if (pathLength == str.length()-1) return true;

        boolean hasPath = false;

        if(row>=0 && row<rows && col>=0 &&col<cols && visited[row][col]==0 && chars[row][col]==str.charAt(pathLength)) {
            ++pathLength;
            visited[row][col] = 1;
            hasPath = solve(visited, chars, rows, cols, row-1, col, str, pathLength) ||
                    solve(visited, chars, rows, cols, row+1, col, str, pathLength) ||
                    solve(visited, chars, rows, cols, row, col-1, str, pathLength) ||
                    solve(visited, chars, rows, cols, row, col+1, str, pathLength);
            if (!hasPath) {
                --pathLength;
                visited[row][col] = 0;
            }
        }
        return hasPath;

    }


}
